#ifndef __BINARYSORT_TREE_H__
#define __BINARYSORT_TREE_H__

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    Node(int);
    ~Node();

    int val;
    Node *lchild, *rchild;
    int high;
};
Node::Node(int v)
    : val(v), high(0), lchild(nullptr), rchild(nullptr)
{
}
Node::~Node()
{
    lchild = rchild = nullptr;
    val = 0;
}

int getHigh(Node *p) 
{
    if (nullptr == p) return -1;
    return p->high;
}

Node *RR(Node *p)
{
    Node *pl = p->lchild;
    p->lchild = pl->rchild;
    pl->rchild = p;
    p->high = std::max(getHigh(p->lchild), getHigh(p->rchild)) + 1;
    pl->high = std::max(getHigh(pl->lchild), p->high) + 1;
    return pl;
}

Node *LL(Node *p)
{
    Node *pr = p->rchild;
    p->rchild = pr->lchild;
    pr->lchild = p;
    p->high = std::max(getHigh(p->lchild), getHigh(p->rchild)) + 1;
    pr->high = std::max(getHigh(pr->rchild), p->high) + 1;
    return pr;
}

Node *LR(Node *p)
{
    p->lchild = LL(p->lchild);
    return RR(p);
}

Node *RL(Node *p)
{
    p->rchild = RR(p->rchild);
    return LL(p);
}

Node *insert(Node *root, int v)
{
    if (nullptr == root)
        return (root = new Node(v));
    else if (v < root->val)
        root->lchild = insert(root->lchild, v);
    else
        root->rchild = insert(root->rchild, v);

    root->high = std::max(getHigh(root->lchild), getHigh(root->rchild))+1;

    if (2 == getHigh(root->lchild) - getHigh(root->rchild))
    {
        if (v < root->lchild->val)
            root = RR(root);
        else
            root = LR(root);
    }
    else if (2 == getHigh(root->rchild) - getHigh(root->lchild))
    {
        if (v < root->rchild->val)
            root = RL(root);
        else
            root = LL(root);
    }
    return root;
}

Node *del(Node *root, int v)
{
    if (!root)
        return nullptr;
    if (v == root->val)
    {
        if (nullptr == root->rchild)
        {
            Node *tmp = root;
            root = root->lchild;
            delete(tmp);
            return root;
        }
        else
        {
            Node *tmp = root->rchild;
            while (tmp->lchild)
                tmp = tmp->lchild;
            root->val = tmp->val;
            root->rchild = del(root->rchild, tmp->val);
        }       
    }
    else if (v < root->val)
        root->lchild = del(root->lchild, v);
    else
        root->rchild = del(root->rchild, v);
    
    root->high = std::max(getHigh(root->lchild), getHigh(root->rchild)) + 1;
    if (2 == getHigh(root->rchild) - getHigh(root->lchild))
    {
        if (getHigh(root->rchild->rchild) >= getHigh(root->rchild->lchild))
            root = LL(root);
        else
            root = RL(root);       
    }
    else if (2 == getHigh(root->lchild) - getHigh(root->rchild))
    {
        if (getHigh(root->lchild->lchild) >= getHigh(root->lchild->rchild))
            root = RR(root);
        else
            root = LR(root);
    }
    return root;
}

Node *find(Node *root, int v)
{
    while (nullptr != root && root->val != v)
    {
        if (v < root->val)
            root = root->lchild;
        else
            root = root->rchild;
    }
    return root;
}

void inOrder(Node *root)
{
    if (root)
    {
        inOrder(root->lchild);
        cout << "val:" << root->val << " high:" << root->high;
        if (root->lchild)
            cout << " lchild:" << root->lchild->val;
        if (root->rchild)
            cout << " rchild:" << root->rchild->val;
        cout << endl; 
        inOrder(root->rchild);
    }
}

#endif